/*
 * Author: doe300
 *
 * See the file "LICENSE" for the full license governing this code.
 */
#ifndef VC4C_AVAILABLE_EXPRESSION_ANALYSIS
#define VC4C_AVAILABLE_EXPRESSION_ANALYSIS

#include "../Expression.h"
#include "../performance.h"
#include "Analysis.h"

namespace vc4c
{
    namespace analysis
    {
        /*
         * Analyses the available expressions within a single basic block.
         *
         * An available expression at a given point in the program is an expression that already has been calculated
         * (and whose result has not yet been overridden) and therefore does not need to be recalculated again.
         *
         * See also: https://en.wikipedia.org/wiki/Available_expression
         *
         */
        class AvailableExpressionAnalysis : public LocalAnalysis<AnalysisDirection::FORWARD, AvailableExpressions,
                                                FastMap<const Local*, FastSet<std::shared_ptr<Expression>>>>
        {
        public:
            explicit AvailableExpressionAnalysis();

            /*
             * For an instruction reading a, b and writing c:
             *
             * - the available expression for c is re-set to the current instruction
             *
             * NOTE: Usage of this function directly and dropping of old results is highly recommended over running the
             * analysis over the whole block!
             *
             * Returns the available expressions for the instruction and the expression generated by the instruction, if
             * any.
             */
            static std::pair<AvailableExpressions, std::shared_ptr<Expression>> analyzeAvailableExpressions(
                const intermediate::IntermediateInstruction* instr, const AvailableExpressions& previousExpressions,
                FastMap<const Local*, FastSet<std::shared_ptr<Expression>>>& cache, unsigned maxExpressionDistance);

            static std::string to_string(const AvailableExpressions& expressions);

            /**
             * Writes the expression graph to the given file via the DebugGraph interface
             */
            static void dumpGraph(const AvailableExpressions& expressions, const std::string& fileName);

        private:
            /*
             * For an instruction reading a, b and writing c:
             *
             * - the available expression for c is re-set to the current instruction
             */
            static AvailableExpressions analyzeAvailableExpressionsWrapper(
                const intermediate::IntermediateInstruction* instr, const AvailableExpressions& previousExpressions,
                FastMap<const Local*, FastSet<std::shared_ptr<Expression>>>& cache);
        };
    } /* namespace analysis */
} /* namespace vc4c */

#endif /* VC4C_AVAILABLE_EXPRESSION_ANALYSIS */
